package com.list;

/**
 * 有哨兵的双向循环链表:
 * 双向链表有前驱与后继,循环链表有表尾指向表头,那么带哨兵就是从表头直接指向表尾
 * 即 head.next.prev = 最后一个元素
 * <p>
 * head.next       为第一个元素
 * head.next.prev  为最后一个元素
 */
public class CirDoubLinkedWithSent implements ILinkedList {

    LinkedNode head;

    @Override
    public void insert(int key) {
        LinkedNode node = new LinkedNode(key);
        if (isEmpty()) {
            head.next = node;
            head.next.next = node;
            head.next.prev = node;
        } else {
            //把 node 的逻辑弄通
            node.next = head.next;
            node.prev = head.next.prev;
            //处理最后的一个节点的指向问题
            head.next.prev.next = node;
            head.next.prev = node;
            //将 node 真正的放入链表
            head.next = node;
        }
    }

    @Override
    public int delete() {
        assert !isEmpty();
        int key = head.next.prev.key;
        head.next.prev = head.next.prev.prev;
        head.next.prev.prev.next = head.next;
        return key;
    }

    @Override
    public boolean isEmpty() {
        return head.next == null;
    }

    public CirDoubLinkedWithSent() {
        head = new LinkedNode(-1);
    }
}
